package leetcode.editor.cn;

import arithmetic2.T_035_SearchInFotatedSortedArrayTarget;

//[33]搜索旋转排序数组
public class SearchInRotatedSortedArray33{
public static void main(String[] args) {
   Solution solution = new SearchInRotatedSortedArray33().new Solution();
    int search = solution.search(new int[]{4, 5, 6, 7, 8, 1, 2, 3}, 8);
    System.out.println("SearchInRotatedSortedArray33:main:" + search);

}

  //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
      /**
       * @see T_035_SearchInFotatedSortedArrayTarget
       *
       * 题目给出的是“旋转排序数组”，是“部分有序数组”，我们同样可以一次排除一半或者一半以上元素的方法，即二分查找法。
       * <P>
       * 二分查找法的本质是排除法，是“减而治之”的算法思想的体现，而“二分”只是手段，二分保证了“熵”最大，即在没有任何有效信息的时候，平分是最好的方案。
       * 思路清楚了以后，我们就得确定“有序数组”存在在“原始数组”的哪个子区间里，下面提供了两个比较标准：
       * <P>>
       * 1、中间元素和左边界比较，可以确定出一个区间有序，另一个区间无序；
       *
       * 2、中间元素和右边界比较，也可以确定出一个区间有序，另一个区间无序。
       *
       * 根据 target 落在有序区间或者无序区间进行分类讨论，每一次讨论可以缩小将近一半的搜索区间。
       * 这是解这道题的关键。根据这两个比较标准就能写出两版不同的代码。
       *
       * 作者：liweiwei1419
       * 链接：https://leetcode-cn.com/problems/search-in-rotated-sorted-array/solution/er-fen-fa-python-dai-ma-java-dai-ma-by-liweiwei141/
       *
       */
    public int search(int[] nums, int target) {
        if (nums == null || nums.length < 1)return 0;

        int left = 0;
        int right = nums.length - 1;
        while (left <= right){
            int mid = left + (right - left)/2;
            int midVal = nums[mid];
            if (target == midVal){
                return mid;
            }else if ( midVal < nums[right] ){//right 有序
                if (target > midVal && target <= nums[right]){//在右边
                    left = mid + 1;
                }else {//在左边
                    right = mid - 1;
                }
            }else {//左边 有序
                if (target >= nums[left] && target < midVal){//在左边
                    right = mid - 1;
                }else {
                    left = mid + 1;
                }
            }

        }

        return -1;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}